#include <iostream>
#include "Tree.h"
#include <queue>
#include <vector>
#include <deque>
using namespace std;
TreeNode* result;
void Tree::createTree()
{
	queue<TreeNode*> buffer;
	this->root = new TreeNode();
	cout << "请输入根节点的值，输入9999退出" << endl;
	cin >> this->root->value;
	buffer.push(root);
	while (true) {
		TreeNode *temp = buffer.front();
		buffer.pop();
		cout << "请输入左子树的值，输入9999退出" << endl;
		int l, r = 0;
		cin >> l;
		if (l >= 9999)
            break;
        TreeNode* lc = new TreeNode(l);
        temp->lc = lc;
        lc->parent = temp;
        this->_size++;
        cout << "请输入右子树的值，输入9999退出" << endl;
        cin >> r;
        if (r >= 9999)
            break;
        TreeNode* rc = new TreeNode(r);
        temp->rc = rc;
        rc->parent = temp;
        this->_size++;
        buffer.push(lc);
        buffer.push(rc);
	}
}

void Tree::traTree(TreeNode* t)
{
    if (t == NULL)
        return;
    cout << t->value << endl;
    traTree(t->lc);
    traTree(t->rc);
}

int Tree::getNum(TreeNode* t)
{
    if (t == NULL)
        return 0;
    return getNum(t->lc) + getNum(t->rc) + 1;
}

void Tree::delNode(int n)
{
    findNode(root, n);
    if(result == NULL)
    {
        cout << "不存在该节点" << endl;
        return;
    }
    _size -= getNum(result);
    TreeNode* resultParent = result->parent;
    if (resultParent->lc->value == result->value)
    {
        resultParent->lc = NULL;
    }
    else
    {
        resultParent->rc = NULL;
    }
    delete(result);
}

TreeNode* Tree::findNode(TreeNode* t, int n)
{
    if (t == NULL)
        return NULL;
    if (t->value == n)
        result = t;
    findNode(t->lc, n);
    findNode(t->rc, n);
}
void Tree::reserveLevelOrder(TreeNode* t)
{
    queue<TreeNode*> buffer;
    deque<deque<int>> result(10);
    int level = 0;
    buffer.push(t);
    bool flag = false;
    while (!buffer.empty())
    {
        int size = buffer.size();
        for (int i = 0; i < size; i++)
        {
            TreeNode *temp = buffer.front();
            if (!flag)
            {
                result[level].push_back(temp->value);
                flag = true;
            }
            else
                result[level].push_front(temp->value);
            buffer.pop();
            if (temp->lc != NULL)
                buffer.push(temp->lc);
            if (temp->rc != NULL)
                buffer.push(temp->rc);
        }
//        cout << result[level].size() << endl;;
        level++;
        flag = false;
    }
    for (int j = level-1; j != -1; j--)
    {
        int lsize = result[j].size();
        for (int m = 0; m < lsize; m++)
        {
            cout << result[j][m] << " ";
        }
        cout << endl;
    }
}
